package Arrays;

public class _287_FindtheDuplicateNumber {
    //solution 1:normal loop search
    //answer:too slow
    public int findDuplicate_0(int[] nums) {
        for (int i=0;i<nums.length;i++) {
            for(int j=0;j<nums.length;j++) {
                if (i != j && nums[i] == nums[j]) {
                    return nums[i];
                }
            }
        }
        return 0;
    }

    //reference solution:use tortoise and hare method
    public int findDuplicate(int[] nums) {
        int tortoise = nums[0];
        int hare = nums[0];
        //get the entrance of the loop
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (hare!=tortoise);

        //hint:when find the entrance,two scan will meet at the duplicated number
        int loop_1 = nums[0];
        int loop_2 = tortoise;
        while (loop_1!=loop_2){
            loop_1 = nums[loop_1];
            loop_2 = nums[loop_2];
        }
        return loop_1;
    }
}
